#include "graph.h"
#include <string.h>

unsigned short getDistance(const unsigned int first, const unsigned int second)
{
	unsigned short f_s = -1, s_f = -1;
	if (first == second)
		return 0;
	for (GraphArc* p = GRAPH.cities[first].first_arc;
		p; p = p->next)
	{
		if (p->to != second)
			continue;
		f_s = p->distance;
		break;
	}
	for (GraphArc* p = GRAPH.cities[second].first_arc;
		p; p = p->next)
	{
		if (p->to != first)
			continue;
		s_f = p->distance;
		break;
	}
	if (f_s == s_f)
		return f_s;
	return (unsigned short)(-1);
}
unsigned int Path[MAX_CITY_COUNT];
int D[MAX_CITY_COUNT];//shortest distances(sd)
bool S[MAX_CITY_COUNT];//whether the shortest distance has been confirmed
unsigned int* shortest_distance_DIJ(const int v0)
{
	memset(S, 0, sizeof(S));
	memset(D, 0, sizeof(D));
	memset(Path, 0, sizeof(Path));
	int v, i;
	//init loop
	for (v = 0; v < GRAPH.city_count; v++) {
		S[v] = false;//init: no sd found
		D[v] = getDistance(v0, v);//init: distance via only ONE arc
		Path[v] = (D[v] > 0) ? v0 : -1;
	}
	S[v0] = true;
	D[v0] = 0;
	//init finished: main loop
	for (i = 0; i < GRAPH.city_count; i++)
	{
		unsigned int min = -1;
		for (int w = 0; w < GRAPH.city_count; w++)
		{
			if (S[w])
				continue;
			if ((unsigned int)D[w] >= min)
				continue;
			v = w;
			min = D[w];
		}
		S[v] = true;
		for (int w = 0; w < GRAPH.city_count; w++)
		{
			if (S[w])continue;
			long candidate = D[v]+getDistance(v, w);
			if (candidate >= (long)D[w])
				continue;
			D[w] = candidate;
			Path[w] = v;
		}
	}
	return D;
}

